package com.thread.thread.Test;

import java.util.Arrays;

public class Test2 {

	public static void main(String[] args)  throws Exception{

		int a[]={7,20,7,0,11,18};

		QuickSort(a, 0,5);
		System.out.println(Arrays.toString(a));
	}

	public static void QuickSort(int[] A, int L, int R){
		if(L < R){
			int pivot = A[L];//最左边的元素作为中轴元素
			//初始化时小于等于pivot的部分，元素个数为0
			//大于pivot的部分，元素个数也为0
			int i = L, j = L+1;
			while(j <= R){
				if(A[j] <= pivot){
					i++;
					swap(A, i, j);
					j++;//j继续向前，扫描下一个
				}else{
					j++;//大于pivot的元素增加一个
				}
			}
			//A[i]及A[i]以前的都小于等于pivot
			//循环结束后A[i+1]及它以后的都大于pivot
			//所以交换A[L]和A[i],这样我们就将中轴元素放到了适当的位置
			swap(A, L, i);
			QuickSort(A, L, i-1);
			QuickSort(A, i+1, R);
		}
	}
	public static void  swap(int a[],int left,int right){
		int temp=a[right];
		a[right]=a[left];
		a[left]=temp;
	}

}

